package mo.tags.dp;

public class L5 {

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int start = 0, end = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            int len1 = palindromeLength(s, i, i, len);
            int len2 = palindromeLength(s, i, i+1, len);
            int curMax = Math.max(len1, len2);
            if (curMax > (end - start)) {
                start = i - (curMax-1) / 2;
                end = i + (curMax / 2);
            }
        }
        return s.substring(start, end+1);
    }

    private int palindromeLength(String s, int left, int right, int len) {
        while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }



}
